package com.chapter13;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

import com.hw.collection.GenHeap;
import com.hw.collection.Heap;
import com.hw.collection.Minheap;
import com.utility.Dictionary;
import com.utility.Point;

public class HashOperation {
	
	
	/*
	 * problem 1 - ToDo
	 */
	public List<String> getAnagrams(String s){
		Map<Character,Integer> m=new HashMap<Character,Integer>();
		for(int i=0;i<s.length();i++){
			char c=s.charAt(i);
			if(c==' ')
				continue;
			if(m.containsKey(i)){
				m.put(c, m.get(s.charAt(i))+1);
			}
			else
				m.put(c, 1);
		}
		List<String> anagram=new ArrayList<String>();
		String path="";
		Map<String,List<String>> dict=Dictionary.readDictionary(path);
		//filter the dictionary
		Map<String,List<String>> filter= new HashMap<String,List<String>>();
		for(Entry<String,List<String>> entry:dict.entrySet()){
			if(isContains(entry.getKey(),m)){
				filter.put(entry.getKey(), entry.getValue());
			}
		}
		return anagram;
	}
	
	public boolean isContains(String s,Map<Character,Integer> m){
		Map<Character,Integer> temp=new HashMap<Character,Integer>();
		for(int i=0;i<s.length();i++){
			char c=s.charAt(i);
			if(temp.containsKey(i)){
				temp.put(c, temp.get(s.charAt(i))+1);
			}
			else
				temp.put(c, 1);
		}
		for(Entry<Character,Integer> entry:temp.entrySet()){
			if(entry.getValue()>m.get(entry.getKey()))
				return false;
		}
		return true;
	}
	public boolean checkifPalindromePossible(String s){
		int map=0;
		for(int i=0;i<s.length();i++){
			int num=s.charAt(i)-'a'+1;
			map=map^(1<<num);
		}
		if(isPowerofTwo(map))
			return true;
		return false;
	}
	
	public boolean isPowerofTwo(int num){
		if((num & (num-1))==0)
			return true;
		return false;
	}
	
	public void testcheckifPalindromePossible(){
		String[] s={"hello","edified","levle","roatort","earllraa"};
		for(String str : s){
			System.out.println(checkifPalindromePossible(str));
		}
	}
	
	/*
	 * problem 6
	 */
	
	public List<String> findKmostFreqQueries(String [] A,int K){
		Map<String, Integer> freq=new HashMap<String,Integer>();
		for(int i=0;i<A.length;i++){
			if(freq.containsKey(A[i]))
				freq.put(A[i], freq.get(A[i])+1);
			else
				freq.put(A[i], 1);
		}
		
		Comparator<Entry<String,Integer>> com=new EntrySetComparator<Entry<String,Integer>>();
		Heap<Entry<String,Integer>> h=new GenHeap<Entry<String,Integer>>(K,com);
		for(Entry<String,Integer> entry:freq.entrySet()){
			if(h.size()<K){
				h.add(entry);
			}
			else{
				if(entry.getValue()>h.peek().getValue()){
					h.delete();
					h.add(entry);
				}
			}
		}
		
		int sizz=h.size();
		List<String> l = new ArrayList<String>();
		for(int i=0;i<sizz;i++){
			l.add(h.delete().getKey());
		}
		
		return l;
		
	}
	
	public void testfindKmostFreqQueries(){
		String [] A={"abc","abc","abc","abc","abc","abc","bcd","bcd","bcd","bcd","he","ui"};
		List<String> l=findKmostFreqQueries(A,2);
		System.out.println(l);
	}
	
	/*
	 * problem 7
	 */
	public int GCD(int a, int b) {
		   if (b==0) return a;
		   return GCD(b,a%b);
		}
	
	public Line findLine(Point p1, Point p2){
		Line line=new Line();
			line.Mnum=p1.getY()-p2.getY();
			line.Mden=p1.getX()-p2.getX();
			line.Cnum=p2.getY()*p1.getX()-p2.getX()*p1.getY();
			line.Cden=p1.getX()-p2.getX();
			int Mgcd=GCD(line.Mden,line.Mnum);
			line.Mden=line.Mden/Mgcd;
			line.Mnum=line.Mnum/Mgcd;
			
			int Cgcd=GCD(line.Cden,line.Cnum);
			line.Cden=line.Cden/Cgcd;
			line.Cnum=line.Cnum/Cgcd;
			if(line.Mden==0){
				line.Mnum=p1.getX();
				line.Cnum=p1.getX();
				return line;
			}
			if(line.Mnum/(double)line.Mden<0){
				line.Mnum=-1*Math.abs(line.Mnum);
				line.Mden=Math.abs(line.Mden);
			}
			if(line.Mnum/(double)line.Mden>0){
				line.Mnum=Math.abs(line.Mnum);
				line.Mden=Math.abs(line.Mden);
			}
			if(line.Cnum/(double)line.Cden<0){
				line.Cnum=-1*Math.abs(line.Cnum);
				line.Cden=Math.abs(line.Cden);
			}
			if(line.Cnum/(double)line.Cden>0){
				line.Cnum=Math.abs(line.Cnum);
				line.Cden=Math.abs(line.Cden);
			}
			
		return line;
	}
	
	public boolean isOnLine(Line line, Point p){
		
		if(line.Mden==0 && line.Mnum==p.getX()){
			return true;
		}
		double m=line.Mnum/(double)line.Mden;
		double c=line.Cnum/(double)line.Cden;
		if(m*p.getX()+c-p.getY()==0)
			return true;
		
		return false;
	}
	public int findMaxPointsonLine(Point[] p){
		int maxcount=0;
		Map<Line,Integer> freq=new HashMap<Line,Integer>();
		Map<Line,Integer> firstOc=new HashMap<Line,Integer>();
		for(int i=0;i<p.length-1;i++){
			for(int j=i+1;j<p.length;j++){
				Line line=findLine(p[i],p[j]);
				if(firstOc.containsKey(line) && firstOc.get(line)<i)
					continue;
				if(!freq.containsKey(line)){
					firstOc.put(line, i);
					int count=2;
					freq.put(line, count);
				}
				else{
					int count=freq.get(line)+1;
					if(maxcount<count)
						maxcount=count;
					freq.put(line, count);
				}
				
				
				
			}
		}
		return maxcount;
	}
	
	public void testfindMaxPointsonLine(){
		int[] x={-2,-1,1,2,3,5,6,7,8,9,10,11,12,13,14};
		int[] y={-3,-1,3,5,7,15,18,21,24,0,0,1,1,1,1};
		Point[] point=new Point[x.length];
		for(int i=0;i<x.length;i++){
			Point p=new Point(x[i],y[i],0);
			point[i]=p;
		}
		System.out.println(findMaxPointsonLine(point));
	}
	/*problem 8
	 * 
	 * 
	 */
	public int findClosestDistance(String[] A){
		int closest=Integer.MAX_VALUE;
		Map<String,Integer> freq=new HashMap<String,Integer>();
		for(int i=0;i<A.length;i++){
			if(freq.containsKey(A[i])){
				int pos=freq.get(A[i]);
				if(i-pos<closest)
					closest=i-pos;
				freq.put(A[i], i);
			}
			else
				freq.put(A[i], i);
		}
		
		return closest;
	}
	
	
	/*
	 * problem 11
	 */
	
	public int findlongestnonrepeating(int[] A){
		Map<Integer,Integer> lastPos=new HashMap<Integer,Integer>();
		int length=1;
		int beginpos=0;
		for(int i=0;i<A.length;i++){
			if(lastPos.containsKey(A[i])){
				int len=i-beginpos;
				if(len>length){
					length=len;
				}
				beginpos=lastPos.get(A[i])+1;
				
			}
			lastPos.put(A[i], i);
		}
		if(A.length-1-beginpos>length)
			length=A.length-1-beginpos;
		return length;
	}
	
	public void testfindlongestnonrepeating(){
		int[] A={5,7,5,11,13,2,11,19,2,11};
		System.out.println(findlongestnonrepeating(A));
		return;
	}
	
	public List<String> findStringConcats(String s, String[] L){
		Map<String,Boolean> freq=new HashMap<String,Boolean>();
		//preprocessing
		for(int i=0;i<L.length;i++){
			freq.put(L[i], false);
		}
		List<String> l =new ArrayList<String>();
		int Llen=L.length;
		int slen=s.length();
		int llen=L[0].length();
		for(int i=0;i<slen-Llen*llen+1;i++){
			int j=i;
			int curlen=0;
			for(Entry<String,Boolean> e:freq.entrySet())
				freq.put(e.getKey(), false);
			while(true){
				if(curlen==Llen){
					l.add(s.substring(i, j));
					break;
				}
				String temp=s.substring(j, j+llen);
				if(freq.containsKey(temp) && !freq.get(temp)){
					j=j+3;
					freq.put(temp, true);
					curlen++;
				}
				else
					break;
			}
		}
		return l;
	}
	
	public void testfindStringConcats(){
		String[] L={"abc","cdf"};
		String s="abcabccdfcdfabc";
		System.out.println(findStringConcats(s,L));
	}
}
